The present invention generally relates to computing systems, and more specifically, to sort accelerators configured to sort data records of a computer processor.
Computing systems are widely used to process and sort data records stored in a database. A variety of sorting algorithms have been developed to reduce sorting time for improving the processing performance of the computing system. Once such sorting algorithm is referred to as tournament tree sort.
In general, a tournament tree sort is a binary-tree based selection and replacement sort algorithm. Tournament tree sort algorithms allow sorting of keys associated with a data record in a continuous streaming fashion. Incoming keys are entered into the leaf nodes and the keys exit, in sorted order, from the tree's root node. For a set of input records that are initially populated into the leaf nodes, pair-wise comparisons (i.e., individual games or matches) are performed at each tree level until a winning record emerges at the tree root. After the initial round of comparisons and populations, each non-leaf node holds exactly one input key, except the winning key which is sent out of the tree. During a continuous sort, after a winner is removed from the tree, a new input record is inserted at the previous winner's leaf node and is compared (and swapped, if needed) with exactly one non-leaf node at each level, until the tree root is reached and the new winner is determined.
One variation on the conventional tournament tree sort algorithm is referred to as a “parallel sort tournament tree”, which performs two separate tournaments at the same time, i.e. simultaneously. For instance, the system generates two separate and individual tournament trees and performs independent tournaments for each respective tree. The winner of each tournament is then “merged” together and sorted.